<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1：
            输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3, 找到最多5个0,3个1的子集的大小，
            输出：4
            解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 
            其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。
            {"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3

            题目描述：
            1. 找到最多m个0、n个1的最大子集的长度
            2. 数量超出，或者不是最大子集的数量不在计算之内

            
            错误解法：判断是01背包
            1. 和01背包的关系:m个0和n个1的综合就是n * 1 + m * 0 = n,背包总和就是n
            2. strs数组的每一项各自都是可以求和的,比如"01"的和就是1,"0001"求和就是1,"111001"求和就是4,"1"求和就是1
            3. 先各自求和转化为新的数组
            4. 再转化为背包问题,去求和
            以上方法错误的原因：需要计算多少个0和多少个1，如果全部把1和0进行累加，就会无法计算0和1了

            正确解法：判断是01背包
            1. 0是一个背包的容量，1是一个背包的容量，背包的容量有两个维度，就是三维背包问题，物品一个维度，


            五部曲：
            
        */
        var findMaxForm = function(strs, m, n) {
            const len = strs.length
            let dp = new Array(len + 1).fill(0).map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)))
            for (let i = 1; i <= len; i++) {
                let zeroNum = 0
                let oneNum = 0
                for (const str of strs[i - 1]) {
                    if (str === '0') zeroNum++
                    else oneNum++
                }
                // 递归遍历
                for (let j = 0; j <= m; j++) {
                    for (let k = 0; k <= n; k++) {
                        dp[i][j][k] = dp[i - 1][j][k]
                        // 如果当前数字取
                        if (j >= zeroNum && k >= oneNum) {
                            dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeroNum][k - oneNum] + 1)
                        }
                    }
                }
            }
            return dp[len][m][n]
        };
        console.log(findMaxForm(["10", "0001", "111001", "1", "0"], 5, 3));
        // console.log(findMaxForm(["10","0","1"], 1, 1));
        // console.log(findMaxForm(["11","11","0","0","10","1","1","0","11","1","0","111","11111000","0","11","000","1","1","0","00","1","101","001","000","0","00","0011","0","10000"], 90, 60));
    </script>
</body>

</html>